export class _Array {
    constructor(capacity = 10, data = null) {
        this.data = new Array(capacity)
        this.size = 0

        if (data) {
            this.data = new Array(data.length)
            data.forEach((d, i) => this.data[i] = d)
            this.size = data.length
        }
    }

    getSize() {
        return this.size
    }

    getCapacity() {
        return this.data.length
    }

    isEmpty() {
        return this.size === 0
    }

    addLast(e) {  // O(1) 均摊复杂度
        this.add(this.size, e)
    }

    addFirst(e) { // O(n)
        this.add(0, e)
    }

    add(index, e) { // O(n)
        if (index < 0 || index > this.size) {
            throw new Error('Add failed. Require index >= 0 and index < size.')

        }

        if (this.size === this.data.length) {
            this.resize(2 * this.data.length)
        }

        for (let i = this.size - 1; i >= index; i--) {
            this.data[i + 1] = this.data[i]
        }
        this.data[index] = e
        this.size++
    }

    get(index) { // O(1)
        if (index < 0 || index > this.size) {
            throw new Error('Get failed. Index is illegal.')

        }

        return this.data[index]
    }

    getLast() {
        return this.get(this.size - 1)
    }

    getFirst() {
        return this.get(0)
    }

    set(index, e) { // O(1)
        if (index < 0 || index > this.size) {
            throw new Error('Set failed. Index is illegal.')

        }

        this.data[index] = e
    }

    contains(e) { // O(n)
        for (let i = 0; i < this.size; i++) {
            if (this.data[i] === e) {
                return true
            }
        }
        return false
    }

    find(e) { // O(n)
        for (let i = 0; i < this.size; i++) {
            if (this.data[i] === e) {
                return i
            }
        }
        return -1
    }

    remove(index) { // O(n)
        if (index < 0 || index > this.size) {
            throw new Error('Remove failed. Index is illegal.')

        }

        const beRemoved = this.data[index]
        for (let i = index; i < this.size - 1; i++) {
            this.data[i] = this.data[i + 1]
        }
        this.size--

        const newCapacity = Math.floor(this.data.length / 2)
        if (this.size <= this.data.length / 4 && newCapacity !== 0) {
            this.resize(newCapacity)
        }

        return beRemoved
    }

    removeFirst() { // O(n)
        return this.remove(0)
    }

    removeLast() { // O(1)
        return this.remove(this.size)
    }

    removeElement(e) {
        const index = this.find(e)
        if (index !== -1) {
            this.remove(index)
        }

    }

    swap(i, j) {
        if (i < 0 || i > this.size || j < 0 || j > this.size) {
            throw new Error('Swap failed. Index is illegal.')
        }

        const tmp = this.data[i]
        this.data[i] = this.data[j]
        this.data[j] = tmp
    }

    toString() {
        let str = '['

        for (let i = 0; i < this.size; i++) {
            str += this.data[i]

            if (i !== this.size - 1) {
                str += ', '
            }
        }
        str += ']'

        return str
    }

    resize(newCapacity) {
        const newData = new Array(newCapacity)
        for (let i = 0; i < this.data.length; i++) {
            newData[i] = this.data[i]
        }
        this.data = newData
    }

}

/*
    增 O(n)
    删 O(n)
    改 已知索引 O(1) 未知索引 O(n)
    查 已知索引 O(1) 未知索引 O(n)
*/